package com.yun.datastructure.tree.binarytree;

import java.util.Arrays;

public class SegmentTree {
    int[] arr;
    int[] tree;
    int[] lazy;

    public SegmentTree(int[] arr) {
        this.arr = arr;
        tree = new int[4 * arr.length];
        lazy = new int[4 * arr.length];
        build_tree(0, 0, arr.length - 1);
    }

    public void build_tree(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }

        int mid = (start + end) / 2;
        int left_node = 2 * node + 1;
        int right_node = 2 * node + 2;

        build_tree(left_node, start, mid);
        build_tree(right_node, mid + 1, end);
        tree[node] = tree[left_node] + tree[right_node];
    }

    public void update_tree(int idx, int val) {//单点修改
        update_tree(0, 0, arr.length - 1, idx, val);
    }

    public void update_tree(int L, int R, int val) {
        update_tree(0, 0, arr.length - 1, L, R, val);
    }

    public void update_tree(int node, int start, int end, int idx, int val) {
        if (start == end) {
            arr[idx] = val;
            tree[node] = val;
            return;
        }
        int mid = (start + end) / 2;
        int left_node = node * 2 + 1;
        int right_node = node * 2 + 2;
        push_down(node, start, end, mid, left_node, right_node);
        if (idx >= start && idx <= mid) {
            update_tree(left_node, start, mid, idx, val);
        } else {
            update_tree(right_node, mid + 1, end, idx, val);
        }
        tree[node] = tree[left_node] + tree[right_node];
    }

    public void update_tree(int node, int start, int end, int L, int R, int val) {
        if (L <= start && end <= R) {
            tree[node] += (end - start + 1) * val;
            lazy[node] += val;
            return;
        }
        int mid = (start + end) >> 1;
        int left_node = node * 2 + 1;
        int right_node = node * 2 + 2;
        push_down(node, start, end, mid, left_node, right_node);
        if (L <= mid) {
            update_tree(left_node, start, mid, L, R, val);
        }
        if (mid < R) {
            update_tree(right_node, mid + 1, end, L, R, val);
        }
        tree[node] = tree[left_node] + tree[right_node];
    }

    private void push_down(int node, int start, int end, int mid, int left_node, int right_node) {
        if (lazy[node] != 0) {//懒标记向下更新
            tree[left_node] += (mid - start + 1) * lazy[node];
            tree[right_node] += (end - mid) * lazy[node];
            lazy[left_node] += lazy[node];
            lazy[right_node] += lazy[node];
            lazy[node] = 0;
        }
    }

    public int query_tree(int L, int R) {
        return query_tree(arr, tree, 0, 0, arr.length - 1, L, R);
    }

    public int query_tree(int[] arr, int[] tree, int node, int start, int end, int L, int R) {
        if (R < start || end < L) {
            return 0;
        }
        if (L <= start && end <= R) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        int left_node = node * 2 + 1;
        int right_node = node * 2 + 2;
        int sum_left = query_tree(arr, tree, left_node, start, mid, L, R);
        int sum_right = query_tree(arr, tree, right_node, mid + 1, end, L, R);
        return sum_left + sum_right;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        SegmentTree segmentTree = new SegmentTree(arr);
        System.out.println(Arrays.toString(segmentTree.tree));
        System.out.println(Arrays.toString(segmentTree.lazy));
        System.out.println();

        segmentTree.update_tree(0,3,1);

        System.out.println(Arrays.toString(segmentTree.tree));
        System.out.println(Arrays.toString(segmentTree.lazy));
        System.out.println();

        segmentTree.update_tree(0,4);

        System.out.println(Arrays.toString(segmentTree.tree));
        System.out.println(Arrays.toString(segmentTree.lazy));
        System.out.println();
    }
}
